class Solution {
public:
    vector<vector<int>> base;

    void sort(vector<int>& nums, int cur)
    {
        int tmp = pow(10, cur);

        for (auto x : nums)
        {
            if (tmp > x)
            {
                base[0].push_back(x);
                continue;
            }
            base[x / tmp % 10].push_back(x);
        }

        nums.clear();
        for (auto& x : base)
        {
            for (auto y : x)
            {
                nums.push_back(y);
            }
            x.clear();
        }
    }

    int help(vector<int>& nums)
    {
        int ret = 0;
        for (auto x : nums)
        {
            int tmp = 0;
            while (x)
            {
                tmp++;
                x /= 10;
            }
            ret = max(ret, tmp);
        }

        return ret;
    }

    int maximumGap(vector<int>& nums)
    {
        int n = nums.size();
        if (n < 2) return 0;

        base = vector<vector<int>>(10, vector<int>());
        int max_cnt = help(nums);

        for (int i = 0; i < max_cnt; i++)
        {
            sort(nums, i);
        }
        int ret = nums[1] - nums[0];

        for (int i = 2; i < n; i++)
        {
            ret = max(ret, nums[i] - nums[i - 1]);
        }

        return ret;
    }
};